Thực đơn
Thuật_toán_Bellman-Ford Cài đặt BellmanHàm khởi tạo (bước 0)
Không như khi cài đặt thuật toán Dijkstra, do Bellman chấp nhận cạnh âm, việc sử dụng trị -1 không còn đúng nữa. Tạm thời, ta có thể sử dụng trị MAXINT (32767) cho giá trị inf, vì nếu như chi phí đạt đến ngưỡng này, có thể xem như tràn số.
step = 0; for {i...} { mincost[step][i] = inf; previous[step][i] = i; } mincost[step][x] = 0;
Cài đặt hàm Bellman
Chú ý rằng để có thể kết luận được đồ thị có chu trình âm hay không. ta cần chạy đến bước thứ n (nghĩa là đi qua tối đa n+1 đỉnh). Do đó, cấu trúc dữ liệu để lưu cũng cần lưu ý khi khai báo.
bSuccess = false; for (step = 1; step <=n; step ++) // dùng <=n thay vì <n { for(i...) { mincost[step][i] = mincost[step-1][i] previous[step][i] = previous[step-1][i] // tìm các đỉnh j có đường nối từ j -->i // và chi phí bước step-1 của j khác vô cực for (j...) if (...&&...) { // cập nhật lại nếu chi phí bước step của i là vô cực // hoặc chi phí đi qua j: mincost[step-1][j]+a[j][i] //tối ưu hơn if (...||...) { // cập nhật lại chi phí và lưu đỉnh cha } } } // so sánh mincost[step] với mincost[step-1], nếu bằng nhau // kết thúc thành công int bSame = true; for (i...) if (mincost[step][i]!= mincost[step-1][i]) { bSame = false; break; // đã giống nhau,đường đi đã tối ưu if (bSame) break; }
Cấu trúc dữ liệu
int mincost [MAX+1][MAX]; int previous[MAX+1][MAX];
Hàm in kết quả
Nếu nStep = n+1, ta kết luận đồ thị có chu trình âm.
Ngược lại, ta sẽ dò chi phí ngược từ bước nStep-1 đến bước 0 (Do bước nStep có giá trị giống bước nStep-1).
k = y; for (i=nStep-1;i>0;i--) // chừa lại bước cuối { printf("%d <---", k); k = previous[i][k]; // đỉnh trước k } printf("%dn",k); // có thể thêm kiểm tra k == x
Thực đơn
Thuật_toán_Bellman-Ford Cài đặt BellmanLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ lý thuyết đồ thị Thuật ngữ thiên văn học Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật ngữ ngữ âm học Thuật toán sắp xếpTài liệu tham khảo
WikiPedia: Thuật_toán_Bellman-Ford